import java.util.ArrayList;
import java.util.Arrays;

public class MergeIntervals0108_56 {
    public int[][] merge(int[][] intervals) {
        ArrayList<int[]> res = new ArrayList<>();

        Arrays.sort(intervals,((o1, o2) -> o1[0] - o2[0]));

        int start = intervals[0][0];
        int end = intervals[0][1];

        for (int i = 1; i < intervals.length; i++) {

            if(intervals[i][0] <= intervals[i-1][1]){
                start = Math.min(start,intervals[i][0]);
                intervals[i][1] = Math.max(intervals[i][1],intervals[i-1][1]);
                end =intervals[i][1];
            }else {
                int[] r = new int[]{start,end};
                res.add(r);
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }
        res.add(new int[]{start,end});
        return res.toArray(new int[][]{});
    }
}
